package org.example;

/**
 * 稀疏数组和正常数组之间转换
 */
public class SparseSolution {

    public int[][] arr2SparseArr(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) {
            return null;
        }
        int sum = 0;
        for (int[] row : arr) {
            for (int value : row) {
                if (value != 0) {
                    sum ++;
                }
            }
        }
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = arr.length;
        sparseArr[0][1] = arr[0].length;
        sparseArr[0][2] = sum;
        int defaultRow = 1;
        for (int i = 0; i < arr.length; i ++) {
            int[] row = arr[i];
            for (int j = 0; j < row.length; j ++) {
                int value = row[j];
                if (value != 0) {
                    sparseArr[defaultRow][0] = i;
                    sparseArr[defaultRow][1] = j;
                    sparseArr[defaultRow][2] = value;
                    defaultRow ++;
                }
            }
        }
        return sparseArr;
    }

    public int[][] sparseArr2Arr(int[][] sparseArr) {
        if (sparseArr == null || sparseArr.length == 0 || sparseArr[0].length == 0) {
            return null;
        }
        int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }

    public static void printArr(int[][] arr) {
        if (arr == null) {
            return;
        }
        System.out.println("===========================================================");
        for (int[] row : arr) {
            for (int value : row) {
                System.out.printf("%d\t", value);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] arr = new int[6][6];
        arr[2][2] = 1;
        arr[3][4] = 2;
        printArr(arr);
        SparseSolution solution = new SparseSolution();
        int[][] sparseArr = solution.arr2SparseArr(arr);
        printArr(sparseArr);
        int[][] sourceArr = solution.sparseArr2Arr(sparseArr);
        printArr(sourceArr);
    }
}
